package org.yao.datastructure.linkedlist;

/**
 * 双向链表
 *
 * @author yaoxiang29703
 * @since 2021/4/8
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
//        testAdd(singleLinkedList);
//        testAddByRank(doubleLinkedList);
        doubleLinkedList.add(new HeroNode2(2, "甄姬"));
        doubleLinkedList.add(new HeroNode2(1, "后裔"));
        doubleLinkedList.add(new HeroNode2(4, "荆轲"));
        doubleLinkedList.add(new HeroNode2(3, "虞姬"));
        doubleLinkedList.add(new HeroNode2(5, "虞姬"));
        doubleLinkedList.show();
        doubleLinkedList.updateNode(new HeroNode2(3, "haha"));
        doubleLinkedList.updateNode(new HeroNode2(2, "haha"));
        doubleLinkedList.show();
        doubleLinkedList.delNode(3);
        doubleLinkedList.delNode(2);
        doubleLinkedList.show();

    }

    private static void testAddByRank(DoubleLinkedList doubleLinkedList) {
        doubleLinkedList.addByRank(new HeroNode2(2, "甄姬"));
        doubleLinkedList.addByRank(new HeroNode2(1, "后裔"));
        doubleLinkedList.addByRank(new HeroNode2(4, "荆轲"));
        doubleLinkedList.addByRank(new HeroNode2(3, "虞姬"));
        doubleLinkedList.addByRank(new HeroNode2(1, "后裔"));
        doubleLinkedList.show();
    }
}

class DoubleLinkedList {
    /**
     * 头节点
     */
    private HeroNode2 head;

    public DoubleLinkedList() {
        head = new HeroNode2(0, "头");
    }

    /**
     * 增加一个节点，直接加到最后
     *
     * @param node
     */
    public void add(HeroNode2 node) {
        HeroNode2 temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }
        temp.setNext(node);
        node.setPrev(temp);
    }

    /**
     * 打印所有节点
     */
    public void show() {
        HeroNode2 temp = head;
        while (temp.getNext() != null) {
            System.out.println(temp.getNext());
            temp = temp.getNext();
        }
    }

    /**
     * 根据排名插入，如果已存在则提示
     */
    public void addByRank(HeroNode2 node) {
        // 从头节点开始遍历
        HeroNode2 temp = head;
        while (temp.getNext() != null) {
            // 判断是否已存在
            if (temp.getNext().getRank() == node.getRank()) {
                System.out.printf("排名为%d的英雄已存在\n", node.getRank());
                return;
            }
            // 插入节点排名小于下一个节点的排名 则插入
            if (temp.getNext().getRank() > node.getRank()) {
                // 将插入节点的next指向temp的下一个节点，这一步一定要在前面 否则会循环引用
                node.setNext(temp.getNext());
                // 将temp的下一个节点prev指向node
                temp.getNext().setPrev(node);
                // 将temp的next指向插入节点
                temp.setNext(node);
                //将当前节点的prev指向temp
                node.setPrev(temp);
                //
                return;
            }
            temp = temp.getNext();
        }
        // 遍历没找到就放大temp后面
        temp.setNext(node);
        node.setPrev(temp);
    }

    /**
     * 删除一个节点
     *
     * @param rank
     */
    public void delNode(int rank) {
        // 判断是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空！");
        }
        // 删除标记
        boolean flag = false;
        // 双向连边删除不需要借助别的节点
        HeroNode2 temp = head.getNext();
        while (temp != null) {
            if (temp.getRank() == rank) {
                // 判断是否是最后一个节点
                if (temp.getNext() == null) {
                    temp.getPrev().setNext(null);
                    temp.setPrev(null);

                } else {
                    // temp下一个节点的prev指向temp的prev
                    temp.getNext().setPrev(temp.getPrev());
                    // temp上一个节点的next指向temp的next
                    temp.getPrev().setNext(temp.getNext());
                }

                flag = true;
            }
            temp = temp.getNext();
        }
        if (!flag) {
            System.out.println("未找到对应节点！");
        } else {
            System.out.println("删除成功");
        }

    }

    /**
     * 更新一个节点
     *
     * @param node
     */
    public void updateNode(HeroNode2 node) {
        // 判断是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空！");
        }
        // 更新标记
        boolean flag = false;
        // 更新一个节点，需要建立四条关系
        HeroNode2 temp = head.getNext();
        while (temp != null) {
            if (temp.getRank() == node.getRank()) {
                //判断节点是否是最后一个节点
                if (temp.getNext() == null) {
                    node.setPrev(temp.getPrev());
                    temp.getPrev().setNext(node);
                } else {
                    // 新节点的next节点指向temp节点的next
                    node.setNext(temp.getNext());
                    // temp的next节点的prev指向新节点node
                    temp.getNext().setPrev(node);
                    // temp节点的next指向当前节点的下一个节点
                    temp.getPrev().setNext(node);
                    // 新节点node 的prev指向temp.prev
                    node.setPrev(temp.getPrev());
                }
                flag = true;
            }
            temp = temp.getNext();
        }
        if (!flag) {
            System.out.println("未找到对应节点！");
        } else {
            System.out.println("更新成功");
        }

    }

}

class HeroNode2 {
    private int rank;
    private String name;
    /**
     * 指向下一个节点
     */
    private HeroNode2 next;
    /**
     * 指向前一个节点
     */
    private HeroNode2 prev;

    public HeroNode2(int rank, String name) {
        this.rank = rank;
        this.name = name;
    }

    public HeroNode2 getNext() {
        return next;
    }

    public void setNext(HeroNode2 next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "rank=" + rank +
                ", name='" + name + '\'' +
                '}';
    }

    public int getRank() {
        return rank;
    }

    public void setRank(int rank) {
        this.rank = rank;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode2 getPrev() {
        return prev;
    }

    public void setPrev(HeroNode2 prev) {
        this.prev = prev;
    }
}